from pythonds.graphs import Vertex, Graph, State

from pythonds.timeit import timer


# 第1步，构建各点的连接情况
def gen_legal_moves(x, y, bd_size) -> list:
    new_moves = []
    move_offsets = [
        (-1, -2),
        (-1, 2),
        (-2, -1),
        (-2, 1),
        (1, -2),
        (1, 2),
        (2, -1),
        (2, 1),
    ]

    for step in move_offsets:
        new_x = x + step[0]
        new_y = y + step[1]
        if legal_coord(new_x, bd_size) and legal_coord(new_y, bd_size):
            new_moves.append((new_x, new_y))
    return new_moves


def legal_coord(t, bd_size) -> bool:
    return t >= 0 and t < bd_size


def knight_graph(bd_size):
    kt_graph = Graph()
    for row in range(bd_size):
        for col in range(bd_size):
            node_id = post_to_id(row, col, bd_size)
            new_postions = gen_legal_moves(row, col, bd_size)
            for edge in new_postions:
                nid = post_to_id(edge[0], edge[1], bd_size)
                kt_graph.add_edge(node_id, nid)

    return kt_graph


def post_to_id(row, col, bd_size) -> int:
    return row * bd_size + col


# 第2步 骑士周游的深度优先求解
def knight_tour(path: list, u: Vertex, limit: int) -> bool:
    u.set_state(State.reached)
    path.append(u)

    if len(path) < limit:
        nbr_list = list(u.get_connections())
        i = 0
        done = False
        while i < len(nbr_list) and not done:
            if nbr_list[i].get_state() == State.unreached:
                done = knight_tour(path, nbr_list[i], limit)
            i += 1
        if not done:
            path.pop()
            u.set_state(State.unreached)
    else:
        done = True

    return done


# 启发式技术
# 通过评估下一步的可能步数，评估下一步应该怎么走
# 选择合理走法最多的顶点作为下一个访问顶点的问题在于，它会使骑士在周游的前期就访问位于棋盘中间的格子。
# 当这种情况发生时，骑士很容易被困在棋盘的一边，而无法到达另一边的那些没访问过的格子。
# 首先访问合理走法最少的顶点，则可使骑士优先访问棋盘边缘的格子。
# 这样做保证了骑士能够尽早访问难以到达的角落，并且在需要的时候通过中间的格子跨越到棋盘的另一边。
# 我们称利用这类知识来加速算法为启发式技术。
def order_by_available(n: Vertex):
    res_list = []
    for v in n.get_connections():
        if v.get_state() == State.unreached:
            c = 0
            for w in v.get_connections():
                if w.get_state() == State.unreached:
                    c += 1
            res_list.append((c, v))

    res_list.sort(key=lambda x: x[0])
    return [y[1] for y in res_list]


def knight_tour_better(path: list, u: Vertex, limit):
    u.set_state(State.reached)
    path.append(u)

    if len(path) < limit:
        nbr_list = order_by_available(u)
        i = 0
        done = False
        while i < len(nbr_list) and not done:
            if nbr_list[i].get_state() == State.unreached:
                done = knight_tour_better(path, nbr_list[i], limit)
            i += 1
        if not done:
            path.pop()
            u.set_state(State.unreached)
    else:
        done = True

    return done


# 验证
@timer
def test_1(path, start, limit):
    knight_tour(path, start, limit)


@timer
def test_2(path, start, limit):
    knight_tour_better(path, start, limit)


def test():
    kg = knight_graph(5)
    path = []
    start: Vertex = kg.get_vertex(4)
    test_1(path, start, 25)
    for v in path:
        print("%2d" % v.get_id(), end=" ")
    print()

    kg2 = knight_graph(5)
    path2 = []
    start2: Vertex = kg2.get_vertex(4)
    test_2(path2, start2, 25)
    for v in path2:
        print("%2d" % v.get_id(), end=" ")
    print()
